package leetcode.map;

import java.util.*;

public class Lc2662 {

    final int INF = Integer.MAX_VALUE / 2;

    public int minimumCost(int[] start, int[] target, int[][] specialRoads) {

        int nodeCnt = 0;// 节点个数
        HashMap<String, Integer> nodeMap = new HashMap<>(); //节点i,j映射为x
        nodeMap.put(start[0] + "-" + start[1], nodeCnt++); //起始节点start[0] + "-" + start[1]映射为节点0
        nodeMap.put(target[0] + "-" + target[1], nodeCnt++); //目标节点映射为1
        HashMap<Integer, int[]> origin = new HashMap<>();
        origin.put(0, new int[]{start[0], start[1]});
        origin.put(1, new int[]{target[0], target[1]});

        int s2tCost = Math.abs(start[0] - target[0]) + Math.abs(start[1] - target[1]);
        HashMap<Integer, List<int[]>> nodeNeighbors = new HashMap<>(); //保存节点的后继节点及边权
        ArrayList<int[]> temp = new ArrayList<>();
        temp.add(new int[]{1, s2tCost});
        nodeNeighbors.put(0, temp);

        for (int i = 0; i < specialRoads.length; i++) {
            //先判断这个特殊路径是不是变短了
            int x1 = specialRoads[i][0];
            int y1 = specialRoads[i][1];
            int x2 = specialRoads[i][2];
            int y2 = specialRoads[i][3];
            int cost = specialRoads[i][4];
            if (Math.abs(x1 - x2) + Math.abs(y1 - y2) <= cost) //特殊路径没效，丢掉
                continue;
            String s = x1 + "-" + y1;
            String t = x2 + "-" + y2;
            int s2n = 0, t2n = 0;
            if (nodeMap.containsKey(s)) s2n = nodeMap.get(s);
            else {
                nodeMap.put(s, nodeCnt);
                s2n = nodeCnt++;
                origin.put(s2n, new int[]{x1, y1});
            }
            if (nodeMap.containsKey(t)) t2n = nodeMap.get(t);
            else {
                nodeMap.put(t, nodeCnt);
                t2n = nodeCnt++;
                origin.put(t2n, new int[]{x2, y2});
            }
            List<int[]> neighbor = nodeNeighbors.getOrDefault(s2n, new ArrayList<>());
            neighbor.add(new int[]{t2n, cost});
            nodeNeighbors.put(s2n, neighbor);
        }

        int[][] graph = new int[nodeCnt][nodeCnt];
        for (int i = 0; i < nodeCnt; i++) {
            Arrays.fill(graph[i], INF);
        }
        for (int i = 0; i < nodeCnt; i++) {
            List<int[]> nodes = nodeNeighbors.get(i);
            if (nodes == null) continue;
            for (int[] node : nodes) {
                int j = node[0];
                int cost = node[1];
                if (graph[i][j] > cost)
                    graph[i][j] = cost;
            }
        }
        for (int i = 0; i < nodeCnt; i++) {
            for (int j = 1; j < nodeCnt; j++) {
                if (i == j) continue;
                if (graph[i][j] == INF) {
                    int[] X = origin.get(i);
                    int[] Y = origin.get(j);
                    graph[i][j] = Math.abs(X[0] - Y[0]) + Math.abs(X[1] - Y[1]);
                }
            }
        }
        int[] dist = new int[nodeCnt];
        Arrays.fill(dist, INF);
        dist[0] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>(((o1, o2) -> o1[1] - o2[1]));
        pq.offer(new int[]{0, 0});
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int i = cur[0];
            for (int j = 1; j < nodeCnt; j++) {
                if (dist[j] > dist[i] + graph[i][j]) {
                    dist[j] = dist[i] + graph[i][j];
                    pq.offer(new int[]{j, dist[j]});
                }
            }
        }
        return dist[1];
    }


    public static void main(String[] args) {
        Lc2662 lc2662 = new Lc2662();
        int[] start = {1,1};
        int[] ta = {10,4};
        int[][] s = {{4,2,1,1,3},{1,2,7,4,4},{10,3,6,1,2},{6,1,1,2,3}};
        System.out.println(lc2662.minimumCost(start, ta, s));

    }

}













